package medium;//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
//
// 有效括号组合需满足：左括号必须以正确的顺序闭合。
//
//
//
// 示例 1：
//
//
//输入：n = 3
//输出：["((()))","(()())","(())()","()(())","()()()"]
//
//
// 示例 2：
//
//
//输入：n = 1
//输出：["()"]
//
//
//
//
// 提示：
//
//
// 1 <= n <= 8
//
// Related Topics 字符串 动态规划 回溯
// 👍 1959 👎 0


import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
public class L22 {
    public static List<String> generateParenthesis(int n) {
        //递归，减去多余分支时间复杂度O(n^2)
        List<String> res = new ArrayList<>();
        generateParenthesis(res, n, 0, 0, new StringBuilder());
        return res;
    }

    public static void generateParenthesis(List<String> res, int n, int l, int r, StringBuilder sb) {
        if (sb.length() == 2 * n) {
            res.add(sb.toString());
            return;
        }
        if (l < n) {
            generateParenthesis(res, n, l + 1, r, sb.append("("));
            sb.deleteCharAt(sb.length() - 1);
        }
        if (r < l) {
            generateParenthesis(res, n, l, r + 1, sb.append(")"));
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
